/**
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 *
 * 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1,col1) ，右下角 为 (row2,col2) 。
 * 实现 NumMatrix 类：
 *
 * NumMatrix(int[][] matrix)给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2)返回 左上角 (row1,col1)、右下角(row2,col2) 所描述的子矩阵的元素 总和 。
 *
 * 链接：https://leetcode.cn/problems/range-sum-query-2d-immutable
 */
class NumMatrix {
    // preSum[i][j] 记录矩阵 [0, 0, i, j] 的元素和
    int[][] presum;
    public NumMatrix(int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        presum=new int[row+1][col+1];
        // 构造前缀和矩阵
        for(int i=1;i<=row;i++) {
            for(int j=1;j<=col;j++) {
                // 计算每个矩阵 [0, 0, i, j] 的元素和
                presum[i][j]=presum[i][j-1]+presum[i-1][j]+matrix[i-1][j-1]-presum[i-1][j-1];
            }
        }
    }
    // 计算子矩阵 [x1, y1, x2, y2] 的元素和
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 目标矩阵之和由四个相邻矩阵运算获得
        return presum[row2+1][col2+1]-presum[row2+1][col1]-presum[row1][col2+1]+presum[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */